package demo;

/**
 *    x 的平方根
 */
class Solution37 {
	public int mySqrt(int x) {
		if (x == 0 || x == 1) {
			return x;
		}
		int left = 0, right = x;
		int mid;
		while (left <= right) {
			mid = left + (right - left) / 2;
			if (mid < x / mid) {
				left = mid + 1;
			} else if (mid > x / mid) {
				right = mid - 1;
			} else {
				return mid;
			}
		}
		return right;
	}
}

